//
// Created by francklinson on 2021/7/26 AT 0:05.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minOperations(vector<int> &target, vector<int> &arr) {
        int n = (int) target.size();
        unordered_map<int, int> pos;   // target中，每个数字和位置的映射
        for (int i = 0; i < n; ++i) {
            pos[target[i]] = i;
        }
        vector<int> d;
        for (int val : arr) {
            if (pos.count(val)) {
                // 转化为求最长递增子序列
                int idx = pos[val];
                auto it = lower_bound(d.begin(), d.end(), idx);
                if (it != d.end()) {
                    *it = idx;
                } else {
                    d.push_back(idx);
                }
            }
        }
        return n - d.size();
    }
};

int main() {
    vector<int> target{5, 1, 3};
    vector<int> arr{9, 4, 2, 3, 4};
    Solution solution;
    cout << solution.minOperations(target, arr) << endl;
    return 0;
}

